//Dijkstra算法求源点到其他顶点的最短路径(单源最短路径)【不能处理带有负权值的图；时间复杂度为O(|V|^2)】
/*
    从某一源点开始构建最短路径树
    每次将从源点到新顶点路径长度最短的顶点纳入生成树，直到所有顶点都加入最短路径生成树。(注：加入生成树则代表已找到最短路径)
*/

//注意：Prim算法 和 Dijkstra算法的区别【详见P229】
/*
    1、Prim算法用于求 带权无向图 的最小生成树；而Dijkstra算法用于求 无负权值图 的单源最短路径。
    2、两个算法每次选取的顶点都是该顶点到"某一对象"权值最低，但是这个参照"对象"不同：
        Prim算法是每次要找到相对于 "当前最小生成树" 的距离最短的顶点，然后将该顶点纳入生成树；
        而Dijkstra算法是每次要找到相对于 "源头顶点" 路径长度最短的顶点，然后将该顶点纳入已找到最短路径集合。
*/

#include "ALGraph.h"
#include <cstring>
#include <iostream>

using namespace std;

int MinOfArray(int *dist, bool *isJoin, int size) //返回未加入最短路径树且距离源点最近(dist最小)的顶点
{
    int min = MAX_WEIGHT;
    int index = 0;
    for (int i = 0; i < size; ++i)
    {
        if (!isJoin[i] && min > dist[i])
        {
            min = dist[i];
            index = i;
        }
    }
    return index;
}

int main()
{
    ALGraph G;
    cout << "1:Directed graph  ||  0:Undirected graph\nchoose 1 or 0: ";
    cin >> G.DirStatue; //1:有向图 || 0:无向图
    cout << "input vexnum and arcnum:\n";
    cin >> G.vexnum >> G.arcnum; //确认该图顶点数和边数
    Init(G);                     //初始化图G

    //得到该图的邻接链表
    cout << "please input (x y weight):\n";
    for (int x, y, weight, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y >> weight;
        AddEdge(G, x, y, weight);
    }

    //数组isJoin、dist、path的初始化
    bool isJoin[MaxVertexNum] = {0}; //记录每个顶点是否加入生成树，并初始化都为false
    int dist[MaxVertexNum];          //未加入的顶点加入生成树的最短路径,并初始化都为最大值
    for (int i = 0; i < MaxVertexNum; ++i)
        dist[i] = MAX_WEIGHT;
    int path[MaxVertexNum]; //用于记录最短路径树的路径，并初始化都为-1
    memset(path, -1, sizeof(path));

    cout << "please input the first vertex:\n";
    int V; //每次要加入生成树的顶点的索引，初始化为最短路径生成树的根节点(即源点)
    cin >> V;
    isJoin[V] = true;   //把源点加入生成树
    dist[V] = 0;        //把源点到源点的路径设为0

    //Dijkstra算法
    for (int i = 1; i < G.vexnum; ++i)  //进行n-1轮处理。每一轮处理：循环遍历所有顶点，找到还没确定最短路径且dist最低的顶点加入最短路径生成树
    {
        for (ArcNode *j = FirstNeighbor(G, V); j != nullptr; j = NextNeighbor(G, V, j->adjvex)) //每加入一个顶点就遍历那个顶点拉出的边表，更新dist和path
        {
            if (!isJoin[j->adjvex] && Get_edge_value(G, V, j->adjvex) + dist[V] < dist[j->adjvex])  //【注意：这里就是和Prim算法唯一的区别】若邻接于顶点i的顶点j满足还未加入生成树且dist[i]+arc_weight[i][j] < dist[j]，则更新dist和path。(注：arc_weight[i][j]表示Vi到Vj的弧的权值)
            {
                dist[j->adjvex] = Get_edge_value(G, V, j->adjvex) + dist[V];
                path[j->adjvex] = V;
            }
        }
        V = MinOfArray(dist, isJoin, G.vexnum); //找到dist中最小且还未找到最短路径的顶点加入生成树
        isJoin[V] = true;   //表示顶点已找到最短路径
    }

    //测试代码
    cout << "The Shortest Path Spanning Tree:\n";
    for (int i = 0; i < G.vexnum; ++i)
        if (path[i] != -1)
            cout << '(' << path[i] << ',' << i << ')';
    return 0;
}